package 剑指offer;

import java.util.*;

/**
 * @description:
 * @author: ywk
 * @date: 2020-10-27
 */
public class 数组中相加和为0的三元组 {
    public static void main(String[] args) {
        System.out.println(threeSum(new int[]{-1,0,1,2,-1,-4}));
    }

    public static ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        Map<Object, Object> map = new LinkedHashMap<>();
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < num.length; i++) {
            list.add(num[i]);
        }
        Collections.sort(list);
        for (int i = 0; i < list.size() - 2; i++) {
            int sum = 0;
            for (int j = i + 1; j <  list.size() - 1; j++) {
                sum = list.get(i) + list.get(j);
                for (int k = j + 1; k <  list.size(); k++) {
                        if (sum +list.get(k) == 0) {
                            ArrayList<Integer> list2 = new ArrayList<>();
                            list2.add(list.get(i));
                            list2.add(list.get(j));
                            list2.add(list.get(k));
                            if (map.get(list2) == null) {
                                map.put(list2, 1);
                                result.add(list2);
                            }

                        }


                }
            }
        }

        return result;
    }
}
